Compilers convert a source program that is usually written in a high level language into low level object code, which typically comprises a sequence of machine instructions or assembly language. The constructs in the source program are also converted into a sequence of assembly language instructions in the executable program. To achieve the highest possible efficiency of operation, it is essential to understand exactly how the program executes. This would allow the program developer to concentrate on improving the parts of the program that are inefficient. Consequently information such as the length of time that the program takes to execute, and other statistics about the program execution, at the function level, at the loop level, and at the basic block level must be determined.
The compilers track loops so that the profilers can instrument these loops and collect information about the loops. In order for the compilers to track the loops, they need to perform some analysis on these loops. This analysis determines the location of the loop entry points and the loop exit points. Instrumentation code is then placed at the loop entry and the exit points identified by the analysis phase by the profiler. The instrumentation code allows the collection of information about the loops. An important requirement of instrumentation code is that it must not affect the code that is normally generated by the compiler. Thus, the instrumentation code must be placed after all of the optimizations have been completed. This process is complicated since loops can be nested inside of each other, and exit points can take the control flow out of a loop nest. Moreover, optimization phases may have taken place between the loop analysis and code generation phases that invalidates the information collected during the loop analysis phase. It may not be possible to update this information as loop control structures may have changed or disappeared after the analysis phase due to optimizations.
One prior art solution to this problem is to repeat the loop analysis several times throughout the compilation process. Since this loop analysis phase is carried out in a number of different places, the loops that are detected in each phase will be different from the previous phase because of the optimizations that happen between these phases. It becomes very difficult for the compiler to correlate the loops that are manifesting in the object code with the loops that are present in the source code. This will cause problems in trying to associate the information that is collected about the loops in the object code with the loops that are present in the source code.
One solution that the compilers use is to keep track of all the loop data structures for the whole compilation process. Whenever any optimization happens, the loop data structures are updated to reflect the loops that are present in the object code. This uses a great deal of memory, because the loop data structures must be maintained in memory for the whole compilation process. But for the need to track the loops, these loop data structures could have been eliminated once the loop optimizations have been performed in the compilers. Also, the compilation time increases because whenever an optimization takes places (even when it is not a loop optimization), a check must be performed to determine whether the loop data structures need to be updated, and then perform the updating if the need exists.
The other technique that prior art compilers use to overcome this problem is to perform the loop analysis and loop optimizations right before the code generation, so that any of the loops that have manifested in the object code can be correlated back to the source code. This is not the ideal place for the loop analysis and the loop optimizations to be performed, because it may not produce optimal code. The different phases of the compilation process have to be driven by the observations that the compiler developers make by examining the collected information on the source program that is being compiled. Because the different phases of the compilation process is limited by the information collection process, this lack of information has the effect of producing sub-optimal code for the program since all possible optimizations may not have been performed.
Another problem of the prior art compilers is their placement of the instrumentation code in loop entry and exits points. Some prior art compilers place the instrumentation code after the loop analysis phase, which guarantees accurate placement since the locations of the entry and exits points have not been changed. However, then the compilers perform optimization phases, and the subsequent optimization phases can optimize away the instrumentation code. Thus, this would render subsequent analysis of the code by the developers useless. Moreover, the resulting optimized code produced by the compiler in the presence of this instrumentation may be different than code produced if the instrumentation is not present.
Compilers comprise a number of different phases, and each of these phases transform the program to produce fast executing code through optimizations, and in the process the correlation between the source code loops and object code loops is lost. Thus, there is a need in the art to keep track of the information, so that the correlation is possible between the loops in the object code and the loops in the source code. This is important because the developer will only see the loops that are present in the source code, but only collect information about the loops that are in the object code. Thus, in order for the developer to adjust the source code for optimal performance by observing the behavior of the loops in the object code, the developer needs to be able to correlate the loops in the source code with the loops in the object code. As long as there are problems associated with the instrumentation code generation phase and the loop analysis phase, this will not be possible.
Therefore, there is a need in the art to separate the instrumentation code generation from the loop analysis phases in the compiler, so that each can be performed at their respective appropriate points in the complication process, depending on the requirements that would construct the most optimal code.